// 作业：
// 1、若长度为n的非空线性表采用顺序存储结构，在表的第i个位置插入一个元素，i的合法取值是（  B  ）。
// A. 1<=i<=n
// B. 1<=i<=n+1
// C. 0<=i<=n-1
// D. 0<=i<=n

// 2、对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为x的数据元素。

// 3、线性表（a1,a2,a3...,an）中的元素递增有序且按顺序存储于计算机内，要求设计一个算法，完成用最少时间在表中查找数值为x的元素，若找到则将其与后继元素位置相交换，若找不到则将其插入表中并使表中元素任然递增有序。


#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef int ElemType ;
typedef struct {
	ElemType elem[MAXSIZE];
	int length;
	}SqList;  

	SqList *CreatList(){
		SqList *L;
		L=(SqList *)malloc(sizeof(SqList));
		if(!L)
		return NULL;
		else{
			L->length=0;
			return L;
		}	
		
	}
	//初始化列表
	void AssignSqList(SqList *L){
		int i;
		printf("请为空表赋值：\n（1）输入元素个数：");
		scanf("%d",&L->length);
		printf("(2)按照元素个数依次输入元素的值（各个元素以空格隔开）");
		for(i=0;i<L->length;i++)
		scanf("%d",&L->elem[i]);
	}
	//打印列表
	void OutputSqList(SqList *L){
		int i;
		int s;
		s=L->length;
		printf("顺序表的长度是%d\n",L->length);
		printf("顺序表的元素依次是:");
	    for(i=0;i<s;i++){
		
			printf("%4d",L->elem[i]);
	}
		printf("\n");
		
	}
	//删除重复的所有值
	void  quchong(SqList *L,ElemType value){
		int i;
		if(L->length==0)
		printf("列表为空！");
		else {
			int pos=0;
			for(i=0;i<L->length;i++){
				if(L->elem[i]!=value){
				printf("位置是：%d",pos);
				L->elem[pos]=L->elem[i];
				pos++;
				}
			}
			L->length=pos;
		}
	}
	//查找元素或者插入元素
	void search(SqList *L,ElemType value){
			int i,pos,status=0,j,right;
			if(L->length==0)
			printf("列表为空！");
			else{
				ElemType l=0,r=L->length-1,mid;
				while (l<=r){
					mid=(l+r)/2;
					if(value==L->elem[mid]){
					pos=mid;
					status=1;
					break;
					}
					else if (value<L->elem[mid]){
					r=mid-1;
					pos=r;
					}
					else
					l=mid+1;
				}
			}
			if(status==1){
				L->elem[pos]=L->elem[pos+1];
				L->elem[pos+1]=value;
			}else if (status==0){
				printf("right=%d",pos);
				for(j=L->length-1;j>=pos+1;j--)
					L->elem[j+1]=L->elem[j];
				L->elem[pos+1]=value;
				L->length++;
			}
				
	}

	int main(){
		SqList *L;
		ElemType c=0;
		L=CreatList();
		if(L==NULL)
		printf("初始化顺序表失败");
		else {
		
		printf("初始化顺序表成功！");
		AssignSqList(L);
		// printf("请输入要去重的元素：");
		printf("输入需要查找的元素：");
		scanf_s("%d",&c);
		search(L,c);
		// quchong(L,c);
		OutputSqList(L);
	}
		return 0;
	}
